{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "13a635bd",
   "metadata": {},
   "source": [
    "## 数值区间的模糊排序\n",
    "1. 数值区间分为三种情况\n",
    "2. 第一种：有重叠；\n",
    "3. 第二种：没有重叠；\n",
    "4. 第三种：部分有重叠，部分没有重叠 - 混合型；\n",
    "5. 首先取出数值区间的左端点，将其与pivot比较后进行排列\n",
    "6. 一个疑惑：如何理解“吸收”的概念？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "aa4043d9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n",
      "False\n",
      "1.75 -> [1.5, 2]\n",
      "1.5 -> [0.5, 1.2]\n",
      "2 -> [1, 2]\n"
     ]
    }
   ],
   "source": [
    "## 数值区间定义\n",
    "class Interval:\n",
    "    def __init__(self, a, b):\n",
    "        if a > b:\n",
    "            raise Exception(\"error interval\")\n",
    "        self.begin = a\n",
    "        self.end = b\n",
    "        self.absortionMap = {}\n",
    "\n",
    "    def absorb(self, other_interval):\n",
    "        is_overlap = False\n",
    "        if other_interval is None:\n",
    "            return is_overlap\n",
    "        if self.begin <= other_interval.begin and other_interval.begin <= self.end:\n",
    "            is_overlap = True\n",
    "        if self.begin >= other_interval.begin and self.begin <= other_interval.end:\n",
    "            is_overlap = True\n",
    "        if is_overlap :\n",
    "            overloap_begin = max(self.begin, other_interval.begin)\n",
    "            overloap_end = max(self.end, other_interval.end)\n",
    "            overloap = Interval(overloap_begin, overloap_end)\n",
    "            self.absortionMap[other_interval] = overloap\n",
    "\n",
    "        return is_overlap\n",
    "    \n",
    "    def __str__(self):\n",
    "        return \"[{0}, {1}]\".format(self.begin, self.end)\n",
    "    \n",
    "    def print_points(self):\n",
    "        for key in self.absortionMap:\n",
    "            # print(type(key))        #<class '__main__.Interval'>\n",
    "            # print(key)              #[1.5, 2] -> [begin, end] --> __str__\n",
    "            point_in_overlap = (self.absortionMap[key].begin + \n",
    "                                self.absortionMap[key].end) / 2\n",
    "            print(\"{0} -> {1}\".format(point_in_overlap, key))\n",
    "        print(\"{0} -> {1}\".format(self.end, self))  # 这里的self 在后续外部调用print_point函数时，打印self会调用__str__\n",
    "\n",
    "i1 = Interval(1, 2)\n",
    "i2 = Interval(1.5, 2)\n",
    "i3 = Interval(0.5, 1.2)\n",
    "print(i1.absorb(i2))\n",
    "print(i1.absorb(i3))\n",
    "print(i2.absorb(i3))\n",
    "i1.print_points()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "7c0b75cd",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 区间调整函数\n",
    "def partition_intervals(intervals, pivot_interval):\n",
    "    \"\"\" 与pivot对应区间有重叠，那么就会被吸收掉 \"\"\"\n",
    "    A = []\n",
    "    for interval in intervals:      # 获取不被pivot区间“吸收”的区间\n",
    "        if interval == pivot_interval:\n",
    "            A.append(interval)\n",
    "        elif pivot_interval.absorb(interval) is not True:\n",
    "            A.append(interval)\n",
    "        else:\n",
    "            print(\"{0} absorb {1}\".format(pivot_interval, interval))\n",
    "    i = 0\n",
    "    j = len(A) - 1\n",
    "    while i < j:\n",
    "        if A[i].begin > pivot_interval.begin:\n",
    "            temp = A[i]\n",
    "            A[i] = A[j]\n",
    "            A[j] = temp\n",
    "            j -= 1\n",
    "        else:\n",
    "            i += 1\n",
    "    if A[i].begin > pivot_interval.begin:\n",
    "        i -= 1\n",
    "    return A, i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "fec09f36",
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "def arrange_array_by_pivot(array, pivot):\n",
    "    \"\"\" 将数组分为3部分， 第1部分元素小于pivot, 第二部分元素等于pivot，第三部分元素大于pivot \"\"\"\n",
    "    i = 0\n",
    "    j = len(array) - 1\n",
    "\n",
    "    while i < j:\n",
    "        if array[i] < pivot:\n",
    "            i += 1\n",
    "        elif array[i] >= pivot:\n",
    "            temp = array[j]\n",
    "            array[j] = array[i]\n",
    "            array[i] = temp\n",
    "            j -= 1\n",
    "        \n",
    "    if array[i] < pivot:\n",
    "        i += 1\n",
    "    \n",
    "    k = i\n",
    "    S1 = array[0:i]\n",
    "    j = len(array) - 1\n",
    "\n",
    "    while i < j:\n",
    "        if array[i] == pivot:\n",
    "            i += 1\n",
    "        else:\n",
    "            temp = array[j]\n",
    "            array[j] = array[i]\n",
    "            array[i] = temp\n",
    "            j -= 1\n",
    "    if array[i] == pivot:\n",
    "        i += 1\n",
    "    \n",
    "    S2 = array[k:i]\n",
    "    S3 = array[i:]\n",
    "\n",
    "    return S1, S2, S3\n",
    "    \n",
    "\n",
    "def selection(array, k):\n",
    "    \"\"\" 查找数组中第k小的元素 \"\"\"\n",
    "    if len(array) <= 1:\n",
    "        return array[0]\n",
    "    if k > len(array):\n",
    "        raise Exception('Out of range!')\n",
    "    \n",
    "    pivot = array[0]\n",
    "    is_good_pivot = False\n",
    "\n",
    "    while is_good_pivot != True:\n",
    "        pivot = random.choice(array)\n",
    "\n",
    "        S1, S2, S3 = arrange_array_by_pivot(array, pivot)\n",
    "        if len(S1) <= int((3/4)*len(array)) and len(S3) <= int((3/4)*len(array)):\n",
    "            is_good_pivot = True\n",
    "    \n",
    "    if len(S1) > 0 and k <= len(S1):\n",
    "        return selection(S1, k)\n",
    "    elif len(S2) > 0 and k <= len(S1) + len(S2):\n",
    "        return pivot\n",
    "    else:\n",
    "        return selection(S3, k - len(S1) - len(S2))\n",
    "    raise Exception('error')\n",
    "\n",
    "## 快速排序\n",
    "def quick_sort_intervals(intervals):\n",
    "    if len(intervals) == 0:\n",
    "        return []\n",
    "    if len(intervals) == 1:\n",
    "        return intervals\n",
    "    lefts = []\n",
    "    for interval in intervals:\n",
    "        lefts.append(interval.begin)\n",
    "\n",
    "    left_pivot = selection(lefts, int(len(lefts) / 2))\n",
    "    pivot_interval = None\n",
    "    for interval in intervals:\n",
    "        if interval.begin == left_pivot:\n",
    "            pivot_interval = interval\n",
    "            break\n",
    "    intervals, mark = partition_intervals(intervals, pivot_interval)\n",
    "    first_parts = quick_sort_intervals(intervals[0 : mark + 1])\n",
    "    second_parts = quick_sort_intervals(intervals[mark + 1 : ])\n",
    "    first_parts.extend(second_parts)\n",
    "    return first_parts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "ec5d7b8c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.61, 3.66]\n",
      "[0.32, 6.18]\n",
      "[1.38, 2.92]\n",
      "[3.31, 4.28]\n",
      "[6.61, 8.82]\n",
      "[6.18, 8.51]\n",
      "[2.08, 5.18]\n",
      "[0.46, 4.09]\n",
      "[4.42, 6.98]\n",
      "[7.7, 8.13]\n"
     ]
    }
   ],
   "source": [
    "## 检验算法的示例数据\n",
    "def generate_interval(num):\n",
    "    count = 0\n",
    "    intervals = []\n",
    "    while count < num:\n",
    "        a = float(\"{0:.2f}\".format(random.uniform(0, 10)))\n",
    "        b = float(\"{0:.2f}\".format(random.uniform(0, 10)))\n",
    "        intervals.append(Interval(min(a, b), max(a, b)))\n",
    "        count += 1\n",
    "    return intervals\n",
    "intervals = generate_interval(10)\n",
    "for interval in intervals:\n",
    "    print(interval)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "dd2079cd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2.08, 5.18] absorb [0.61, 3.66]\n",
      "[2.08, 5.18] absorb [0.32, 6.18]\n",
      "[2.08, 5.18] absorb [1.38, 2.92]\n",
      "[2.08, 5.18] absorb [3.31, 4.28]\n",
      "[2.08, 5.18] absorb [0.46, 4.09]\n",
      "[2.08, 5.18] absorb [4.42, 6.98]\n",
      "[6.18, 8.51] absorb [7.7, 8.13]\n",
      "[6.18, 8.51] absorb [6.61, 8.82]\n",
      "3.63 -> [0.61, 3.66]\n",
      "4.13 -> [0.32, 6.18]\n",
      "3.63 -> [1.38, 2.92]\n",
      "4.245 -> [3.31, 4.28]\n",
      "3.63 -> [0.46, 4.09]\n",
      "5.7 -> [4.42, 6.98]\n",
      "5.18 -> [2.08, 5.18]\n",
      "8.105 -> [7.7, 8.13]\n",
      "7.715 -> [6.61, 8.82]\n",
      "8.51 -> [6.18, 8.51]\n"
     ]
    }
   ],
   "source": [
    "A = quick_sort_intervals(intervals)\n",
    "for a in A:\n",
    "    a.print_points()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "env_py38",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.18"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
